package MinAbsoluteSumDiff;

import java.io.*;

/**
 * @className: Solution
 * @Description:
 * @Author: wangyifei
 * @Date: 2022/10/26 16:18
 */
public class Solution {
    public static int BITMAP_CAPACITY = ( 1 << 20) ;
    public static int[] bitMaps = new int[BITMAP_CAPACITY];
    public final static int SHIFT = 5 ;
    public final static int MASK = 0x1F;
    public static void put(int num){
        bitMaps[ num >> SHIFT ] |= 1<<(num & MASK) ;
    }
    public static boolean exists(int num){
        return (bitMaps[ num >> SHIFT] & 1<<(num & MASK)) > 0 ;
    }
    public static int right(int num){
        boolean exists = false ;
        while( num >= 0 ){
            if((bitMaps[num >> SHIFT] & 1<<(num & MASK)) > 0){
                exists = true ;
                break ;
            }
            num --;
        }
        return exists ? num : -1 ;
    }
    public static int left(int num){
       boolean exists = false ;
       while( num>>SHIFT < BITMAP_CAPACITY){
          if((bitMaps[num >> SHIFT] & 1<<(num & MASK) ) > 0){
            exists = true ;
            break ;
          }
          num ++ ;
       }
       return exists ? num : Integer.MAX_VALUE;
    }
    public static int minAbsoluteSumDiff(int[] nums1, int[] nums2) {
        final int MOD = 1000000007;
        int sum = 0 ;
        for(int i = 0 ; i < nums1.length ; i++){
            sum = (sum + Math.abs(nums1[i] - nums2[i]))%MOD;
            put(nums1[i]);
        }
        int left = 0 ;
        int right = 0 ;
        int max = 0 ;
        int maxLength = 0 ;
        int abs = 0 ;
        for(int i = 0 ; i < nums2.length ; i++){
            left = left(nums2[i]);
            right = right(nums2[i]);
            abs = Math.abs(nums1[i] - nums2[i]);
            if(left == Integer.MAX_VALUE){
                max = Math.abs(right - nums2[i]) < abs ? abs - Math.abs(right - nums2[i]) : 0;
            }else if(right == -1){
                max = Math.abs(left - nums2[i]) < abs ? abs - Math.abs(left - nums2[i]) : 0 ;
            }else{
                // 取距离最小的哪里
                max = Math.abs(left - nums2[i]) < Math.abs(right - nums2[i]) ?
                        Math.abs(left - nums2[i])
                        :Math.abs(right - nums2[i]) ;
                // 上面的 max 取最小的那个，下面才能取到最大的那个
                max = max < abs ? abs - max : 0;
            }
            maxLength = (maxLength > max ? maxLength : max);
        }
        return (sum -  maxLength + MOD)%MOD;
    }

    public static void main(String[] args) throws IOException {
        int[] score1 = null ;
        int[] score2 = null ;
        try {
            InputStreamReader isr =
                    new InputStreamReader(new FileInputStream(new File("D:\\workspace\\MyLeetCode\\src\\main\\java\\MinAbsoluteSumDiff\\testNums.txt")));
            BufferedReader br = new BufferedReader(isr);
            String line = null ;
            String[] nums = null ;
            int idx = 0 ;
            while( ( line = br.readLine()) != null){
                nums = line.split(",");
                if(idx == 0){
                    score1 = new int[nums.length];
                    for(int i = 0 ; i < nums.length ; i++){
                        score1[i] = Integer.parseInt(nums[i]);
                    }
                }else{
                    score2 = new int[nums.length];
                    for(int i = 0 ; i < nums.length ; i++){
                        score2[i] = Integer.parseInt(nums[i]);
                    }
                }
                idx ++;
            }

            int ans = minAbsoluteSumDiff(score1 , score2);

            System.out.println(ans);
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
    }
}
